package algorithm.tree.binarytree.base;

import algorithm.tree.binarytree.deep.ComputeTreeDeepNonRecursion;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class TreeUtils {
    public static TreeNode createTree(int[] data) {
        return createTreeNode(data, 0);
    }

    public static int[] createTreeData(TreeNode root) {
        if (root == null) {
            return new int[0];
        } else {
            int deep = ComputeTreeDeepNonRecursion.getDeep(root);
            int[] data = new int[(int) Math.pow(2, deep)];
            Arrays.fill(data, -1);
            fillTreeData(data, root, 0);
            return data;
        }
    }

    private static void fillTreeData(int[] data, TreeNode node, int i) {
        if (node != null) {
            if (i < data.length) {
                data[i] = node.value;
                fillTreeData(data, node.left, 2 * i + 1);
                fillTreeData(data, node.right, 2 * i + 2);
            } else {
                throw new RuntimeException("invalid index");
            }
        } else {
            if (i < data.length) {
                data[i] = -1;
                fillTreeData(data, null, 2 * i + 1);
                fillTreeData(data, null, 2 * i + 2);
            }
        }
    }

    private static String getNodeData(int[] treeData, int index) {
        if (index < treeData.length && treeData[index] != -1) {
            return treeData[index] + "";
        } else {
            return "*";
        }
    }

    private static int getNodeIndex(int currentDeep, int sequence) {
        return (int) (Math.pow(2, currentDeep - 1)) - 1 + sequence;
    }

    public static void printTree(TreeNode root) {
        int[] treeData = createTreeData(root);
        Function<Integer, Integer> getNodeCountInLayer = deep -> (int) Math.pow(2, deep - 1);
        int deep = ComputeTreeDeepNonRecursion.getDeep(root);
        int unitSpan = 2;
        int unitWidth = 2;
        int bottomLayerNodeCount = getNodeCountInLayer.apply(deep);
        double bottomLayerWidth = bottomLayerNodeCount * unitWidth + (bottomLayerNodeCount - 1) * unitSpan;
        int currentDeep = 1;
        List<String> treeInfoList = new ArrayList<>();
        while (currentDeep <= deep) {
            if (currentDeep == deep) {
                StringJoiner joiner = new StringJoiner(" ".repeat(unitSpan));
                int currentLayerNodeCount = getNodeCountInLayer.apply(currentDeep);
                for (int i = 0; i < currentLayerNodeCount; i++) {
                    int index = getNodeIndex(currentDeep, i);
                    String data = getNodeData(treeData, index);
                    joiner.add(String.format("%-" + unitWidth + "s", data));
                }
                treeInfoList.add(joiner.toString());
            } else {
                int currentLayerNodeCount = getNodeCountInLayer.apply(currentDeep);
                double halfSpanWidth = (bottomLayerWidth - currentLayerNodeCount * unitWidth) / (2 * currentLayerNodeCount);
                StringBuilder stringBuilder = new StringBuilder();
                stringBuilder.append(" ".repeat((int) (Math.round(halfSpanWidth * 100) / 100)));
                for (int i = 0; i < currentLayerNodeCount; i++) {
                    int index = getNodeIndex(currentDeep, i);
                    String data = getNodeData(treeData, index);
                    int preLength = (int) Math.round((halfSpanWidth * 2 * i + unitWidth * i + halfSpanWidth) * 100) / 100;
                    int nextSpanWidth = preLength - stringBuilder.length();
                    stringBuilder.append(" ".repeat(nextSpanWidth));
                    stringBuilder.append(data);
                }
                int nextSpanWidth = (int) (bottomLayerWidth - stringBuilder.length());
                stringBuilder.append(" ".repeat(nextSpanWidth));
                treeInfoList.add(stringBuilder.toString());
            }
            currentDeep++;
        }
        System.out.println(treeInfoList.stream().collect(Collectors.joining("\n")));
        ;
    }

    public static void printTree(int[] treeData) {
        printTree(createTree(treeData));
    }

    private static TreeNode createTreeNode(int[] data, int i) {
        if (i < data.length) {
            if (data[i] != -1) {
                TreeNode parent = new TreeNode(i, data[i]);
                parent.setLeft(createTreeNode(data, 2 * i + 1));
                parent.setRight(createTreeNode(data, 2 * i + 2));
                return parent;
            }
        }
        return null;
    }
}
